home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / src / mosmllib / Array2.sml < prev    next >
Encoding:
Text File  |  1997-08-18  |  3.9 KB  |  131 lines  |  [TEXT/R*ch]
  1. (* Array2 -- as of 1995-09-12, 1997-03-12 *)
  2.  
  3. (* Representation of an m * n array: an m-vector of n-arrays (rows),
  4.    and the dimensions (m, n), m = number of rows, n = number of columns. *)
  5.  
  6. (* The implementation below is pretty naive, using the Array and Vector 
  7.    operations and doing more bounds checks than strictly necessary.  *)
  8.  
  9. type 'a array2 = ('a Array.array Vector.vector * int * int) ref 
  10.  
  11. type region = { row : int, col : int, ht : int option, wd : int option}
  12.  
  13. fun fromList [] = ref (Vector.fromList [], 0, 0)
  14.   | fromList (xs1 :: xsr) =
  15.     let val row1 = Array.fromList xs1
  16.     val rowr = List.map Array.fromList xsr
  17.     val cols = Array.length row1
  18.     val vec = 
  19.         if List.all (fn r => Array.length r = cols) rowr then
  20.         Vector.fromList (row1 :: rowr)
  21.         else
  22.         raise Size
  23.     in 
  24.     ref (vec, Vector.length vec, cols)
  25.     end
  26.  
  27. fun array (m, n, x) = 
  28.     ref (Vector.tabulate(m, fn _ => Array.array(n, x)), m, n);
  29.  
  30. fun tabulate (m, n, f) = 
  31.     ref (Vector.tabulate(m, fn i => Array.tabulate(n, fn j => f(i,j))), m, n); 
  32.  
  33. fun dimensions (ref (a,m,n)) = (m,n);
  34.  
  35. fun height (ref (a,m,n)) = m;
  36.  
  37. fun width (ref (a,m,n)) = n;
  38.  
  39. fun sub(ref (a,m,n), i, j) = Array.sub(Vector.sub(a, i), j);
  40.  
  41. fun update(ref (a,m,n), i, j, x) = Array.update(Vector.sub(a, i), j, x);
  42.  
  43. fun row (ref (a, _, _), i) = 
  44.     Array.extract(Vector.sub(a, i), 0, NONE);
  45.  
  46. fun column (ref (a, m, n), j) = 
  47.     if j<0 orelse j>=n then raise Subscript
  48.     else Vector.tabulate(m, fn k => Array.sub(Vector.sub(a, k), j))
  49.  
  50. fun app f (ref (a, _, _)) = 
  51.     Vector.app (Array.app f) a
  52.  
  53. fun appi f (ref (a, _, _), { row, col, ht, wd }) =
  54.     Vector.appi 
  55.           (fn (i, xs) => Array.appi (fn (j, x) => f(i, j, x)) (xs, col, wd))
  56.       (a, row, ht)
  57.  
  58. fun modify f (ref (a, _, _)) = 
  59.     Vector.app (Array.modify f) a
  60.  
  61. fun modifyi f (ref (a, _, _), { row, col, ht, wd }) =
  62.     Vector.appi 
  63.           (fn (i, xs) => Array.modifyi (fn (j, x) => f(i, j, x)) (xs, col, wd))
  64.       (a, row, ht)
  65.  
  66. datatype traversal = RowMajor | ColMajor
  67.  
  68. fun fold RowMajor f b (ref (a, _, _)) = 
  69.     Vector.foldl (fn (xs, res) => Array.foldl f res xs) b a
  70.   | fold ColMajor f b (ref (a, m, n)) = 
  71.     let fun rows j i b = 
  72.         if i >= m then b 
  73.         else rows j (i+1) (f(Array.sub(Vector.sub(a, i), j), b))
  74.     fun cols j b =
  75.         if j >= n then b 
  76.         else cols (j+1) (rows j 0 b)
  77.     in cols 0 b end
  78.  
  79. fun stop len i NONE = 
  80.     if i<0 orelse i>len then raise Subscript
  81.     else len
  82.   | stop len i (SOME n) = 
  83.     if i<0 orelse n<0 orelse i+n>len then raise Subscript
  84.     else i+n;
  85.  
  86. fun foldi RowMajor f b (ref (a, m, n), { row, col, ht, wd }) = 
  87.     Vector.foldli 
  88.            (fn (i, xs, res) => 
  89.            Array.foldli (fn (j,x,res) => f(i,j,x,res)) res (xs,col,wd))
  90.        b (a, row, ht)
  91.   | foldi ColMajor f b (ref (a, m, n), reg as { row, col, ht, wd }) = 
  92.     let val stoprow = stop m row ht
  93.     val stopcol = stop n col wd
  94.     fun rows j i b = 
  95.         if i >= stoprow then b 
  96.         else rows j (i+1) (f(i, j, Array.sub(Vector.sub(a, i), j), b))
  97.     fun cols j b =
  98.         if j >= stopcol then b 
  99.         else cols (j+1) (rows j row b)
  100.     in cols col b end
  101.  
  102. fun copy { src = ref (sa, sm, sn), dst = ref (da, dm, dn), 
  103.        src_reg = { row = src_row, col = src_col, ht, wd }, 
  104.        dst_row, dst_col } =
  105.     let val stoprow = stop sm src_row ht
  106.     fun bottomUp from_row to_row = 
  107.         if from_row < src_row then ()
  108.         else
  109.         (Array.copy { src = Vector.sub(sa, from_row), 
  110.                   si = src_col, len = wd,
  111.                   dst = Vector.sub(da, to_row),
  112.                   di = dst_col };
  113.          bottomUp (from_row-1) (to_row-1))
  114.     fun topDown from_row to_row = 
  115.         if from_row >= stoprow then ()
  116.         else
  117.         (Array.copy { src = Vector.sub(sa, from_row), 
  118.                   si = src_col, len = wd,
  119.                   dst = Vector.sub(da, to_row),
  120.                   di = dst_col };
  121.          topDown (from_row+1) (to_row+1))
  122.     in
  123.     if src_row <= dst_row then (* top dst overlaps with bot src; 
  124.                       copy bottom-up *)
  125.         bottomUp (stoprow-1) (stoprow-1+dst_row-src_row)
  126.     else (* bot dst overlaps with top src; copy top-down *)
  127.         topDown src_row dst_row
  128.     end
  129.  
  130.     
  131.